import javax.swing.tree.TreeNode;
import java.util.HashMap;


/**
 * jdk1.8 HashMap-核心源码解读
 * -------------------------------------------------------------------------
 * HashMap底层实现原理：
 *    HashMap底层采用了（数组+链表+红黑树）实现数据存放
 *   由于HashMap大概率的采用数组+链表存放，而链表的查询时间复杂度为o(n)即全表查询，效率低，
 *   所以在jdk1.8时就引入红黑树当HashMap的table数组的长度>64同时链表个数>8后会转换为数组+红黑树存放，
 *   同时当红黑树的节点数<6时会转换为链表存放。
 * --------------------------------------------------------------------------
 * HashMap get查询时间复杂度：
 *    HashMap的各数据结构的数据查询时间复杂度为：数组 O(1)，链表为O(n)，红黑树为O(logN)
 * -------------------------------------------------------------------------------
 * HashMap扩容机制：
 *    HashMap的默认table数组容量为16当HashMap的table的存储数量达到(table.length*负载因子0.75)的阈值时会自动扩容table容量，
 *   扩容的长度为 table长度的2次方
 *   HashMap扩容时会将原table数组中的数据迁移到新的扩容数组中
 *   同时会采用尾插法将链表拆分为两个链表（高位链表和低位链表）利用key.hash & table.length长度作&运算
 *   (21312421 & 16)即为0
 *   结果==0存放到低位链表
 *   结果==16存放到高位链表
 * --------------------------------------------------------------------------------
 *
 * PS：
 * 一、HashMap线程是不安全的，1.7的hashMap在多线程环境下会存在get()死循环的情况
 *   1.7扩容时在旧表迁移新表时采用头插法会更改旧表的数据结构。多线程环境下get数据会出现死循环导致线程安全问题。
 *   1.8采用尾插法解决了更改数据结构问题。在多线程环境下应当使用ConcurrentHashMap
 *
 * 二、使用HashMap时应指定其长度 new HashMap(100)这样会减少HashMap频繁扩容导致性能问题。
 *   同时在阿里开发手册中对HashMap的使用描述也提到:建议在使用HasHMap时指定其长度
 *   计算公式为 initialCapacity= (需要存放个数/0.75)+1 如果暂时无法确定初始值大小，设置为 16（即默认值）
 * ------------------------------------------------------------
 *
 * @author Zee
 * @version 1.0
 * @date 2021/7/27
 */
public class HashMap<K, V> {

    /**
     * 计算key的hash值
     */
    static final int hash(Object key) {
        int h;
        //计算Hash值 这里将HashCode作有符号位移2的16次方 即hashcode/2的16次方在作^运算;
        //如果key为null 下标直接为0 所以HashMap允许存放key为null当key为null时存放在数组第一的为位置（0）
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    /**
     * HashMap  put方法源码
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    /**
     * HashMap  put方法核心源码
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        java.util.HashMap.Node<K, V>[] tab;
        java.util.HashMap.Node<K, V> p;
        int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            //当table为空获者table长度为0时执行扩容。
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            //if判断中(n-1)&hash计算出table的数组下标位置。n为数组的长度,为什么会n-1?是为了在做&运算后减少hash冲突概率
            //同时判断当前位置tab中是否存有Entry节点数据如果为null则存放到i = (n - 1) & hash数组位置
            tab[i] = newNode(hash, key, value, null);
        else {
            //当以上情况不满足时重点来了（重点，重点，重点，重要事情说三遍）
            //这时证明当前index位置hash冲突，会将数据存放在该index节点的下一节点(next)，
            // 一般情况都是链表存放,采用红黑树的条件概率一般很低
            java.util.HashMap.Node<K, V> e;
            K k;
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                //这里判断key和hash是和当前index的key是否相等如果相等就替换掉旧数据为新数据
                //所以一般情况使用相同的key一般情况为只要不为【对像类型】都会替换旧的key
                //因为key.equals(k)是调用的Object中的equals他使用的 ==的方式比较内存地址是否相等
                //对像==对像肯定是不相等的，因为内存地址不同
                //   注意：
                //      如果要对像之间equals比较相等,那就要对像重写 equals方法，同时也一并重写hashCode方法
                //      因为Set集合在去重时会判断HashCode是否相等
                e = p;
            else if (p instanceof TreeNode)
                //这里判断该节点是否为红黑树 如果为红黑树则将数据存入红黑树中
                e = ((java.util.HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
            else {
                //当以上情况都不满足时则很显然是链表的存放结构
                //1.循环遍历链表中的节点。
                for (int binCount = 0; ; ++binCount) {
                    //2.判断链表的当前节点的下一节点是否为空
                    if ((e = p.next) == null) {
                        //3.如果下一节点为空则将当前的数据(key,value)存放到当前节点的下一节点
                        p.next = newNode(hash, key, value, null);
                        //4.这里判断链表的个数（binCount）是否大于8
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            //如果大于了8这里treeifyBin方法会将链表转换为红黑树（当然这个方法中会判断table的长度要大于了64才会转换）
                            //所以这里转红黑树的条件为数组长度>64同时链表长度>8时才会将链表转换为红黑数
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果下一节点的key相等则结束循环表示该值已经在最后下一节点中
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //这里是以上条件都不满足则表示循环继续遍历下一节点
                    p = e;
                }
            }
            //这个就不用解释了
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //这里++modCount的作用是为了防止 HashMap在遍历的同时又插入新数据。
        //即：同时遍历，同时插入是不被允许的
        //所以当在遍历HashMap时会缓存当前Map的modCount，如果这时再往当前map里面插入了数据。modCount+1
        //循环遍历会判断modCount的值是否发生变化如果发生变化就会抛出异常
        ++modCount;
        //这里put一个数据size会增加1同时判断当前的数组长度是否大于了负载因子0.75的长度。
        if (++size > threshold)
            //如果大于负载因子0.75的长度则执行扩容操作。resize()
            resize();
        afterNodeInsertion(evict);
        return null;
    }

    /**
     * HashMap扩容方法
     *
     * @return
     */
    final java.util.HashMap.Node<K, V>[] resize() {
        java.util.HashMap.Node<K, V>[] oldTab = table;
        //旧table长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //扩容阈值
        int oldThr = threshold;
        //新表的长度
        int newCap;
        //下一次扩容的阈值
        int newThr = 0;
        //下面的代码是计算扩容和扩容阈值同时迁移旧表到新表
        if (oldCap > 0) {
            //这里如果长度 MAXIMUM_CAPACITY= 1 << 30 相当于2的30次方的长度 达到1073741824
            //一般情况谁会在HashMap里面放10亿数据？这个概率是很低的
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                //当达到这个量级也是hashMap的极限存放量也就不在扩容了直接return
                return oldTab;
            }
            //这里newCap为新的容量，这里 oldCap <<1 表示 oldCap*2的1次方 16*2=32 即本次扩容到32
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                //这里将新的扩容阈值oldThr<<1 表示16*0.75*2 下次扩容阈值为24时就会执行扩容操作
                newThr = oldThr << 1;
        } else if (oldThr > 0)
            newCap = oldThr;
        else {
            //计算扩容长度和扩容的阈值
            newCap = DEFAULT_INITIAL_CAPACITY;
            //16*0.75
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //计算下次扩容的阈值
        if (newThr == 0) {
            float ft = (float) newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                    (int) ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes", "unchecked"})
        //这里实例化新扩容的节点数组也是叫作Entry数组
                java.util.HashMap.Node<K, V>[] newTab = (java.util.HashMap.Node<K, V>[]) new java.util.HashMap.Node[newCap];
        table = newTab;
        //以下的代码就是将扩容前的数据迁移到新的newTab中
        if (oldTab != null) {
            //循环遍历旧表
            for (int j = 0; j < oldCap; ++j) {
                java.util.HashMap.Node<K, V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        //如果下一节点为空则插入当前数组下标链表头部
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof java.util.HashMap.TreeNode)
                        //如果该节点为红黑树则用红树存放同split方法中会判断红黑树的节点数是否小6
                        //如果小于6则将红黑数转换为链表
                        ((java.util.HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        //重点来了
                        //Doug Lea老爷子当时怎么会想到这么牛皮的方式
                        //Doug Lea老爷子采用了两个高低位的双向链表将oldTab中的链表分别存放到高低位链表中
                        //同时将低位链表和高位链表头尾相连形成双向链表
                        //为什么这里Doug Lea老爷子要这么干呢？这样做的好处是什么呢？
                        //由于链表的get查询时间复杂度为:O(n)即全表查询 效率较低，所以Doug Lea老爷子就用了这两个双向链表
                        //来存放减少了链表的长度同时查询的性能得到提升牛皮!为Doug Lea老爷子点赞!
                        java.util.HashMap.Node<K, V> loHead = null, loTail = null;
                        java.util.HashMap.Node<K, V> hiHead = null, hiTail = null;
                        java.util.HashMap.Node<K, V> next;
                        do {
                            next = e.next;
                            //计算hash&运算 将小于当旧表数组长度（oldCap） 链表放入到低位链表
                            //(e.hash & oldCap) == 0 这里计算出来的结果==0 如何==oldCap 执行else
                            if ((e.hash & oldCap) == 0) {
                                //存放到低位链表
                                //采用尾插法这里逻辑相对复杂
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            } else {
                                //否则存放到高位链表
                                //采用尾插法这里逻辑相对复杂
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                            //当next不为空继续拆分链表
                        } while ((e = next) != null);

                        if (loTail != null) {
                            loTail.next = null;
                            //将链表存放在低位
                            newTab[j] = loHead;
                        }

                        if (hiTail != null) {
                            hiTail.next = null;
                            //将链表存放在高位
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

}
//为此HashMap的核心源码就到此结束了 get remove 就不用解读了